package com.lg.algorithm.offer;

/**
 * 打印数字组中重复的数字，数组长度为n且数字中的数字都在 0到n-1
 *
 *
 * 1、对数组排序，排序的过程中就可以确定  nlogn
 *
 * 2、找一个空间 n  并遍历数组 n
 *
 * 3、利用原来数组  变量数字 n
 * 检测输入为空
 * 检测输入不合题意
 * 变量数组并将数字放在对应下标上,保证角标过去的数字都检测过
 */
public class FindSameNum {

    static boolean illegal(int [] targetArr){
        for (int i = 0; i < targetArr.length; i++) {
            if(targetArr[i] < 0 || targetArr[i]>targetArr.length-1)
                return true;
        }
        return false;
    }
    static void find(int [] targetArr){
        if(null == targetArr || targetArr.length == 0)
            return;

        if(illegal(targetArr))
            return;

        //数组长度为n 数值为0到n-1，没有重复数字的时候只有一种可能！
        //把相应的位置上放上数，第二次再放的时候校验
        //以游标 i 作为分界, 等于游标的直接过，大于游标的一直交换。
        // 小于游标的，
        // 要么是我已经放好的，即下标等于数，如果对应这个，直接打印，如果不对应这个，那也不会找到它
        // 要么就是找到了重复的，不会找到它，是重复的，那么在前面比较的时候 会把它弄到后面去
        for (int i = 0; i < targetArr.length; i++) {
            while (true) {
                if(targetArr[i] != i){
                    if(targetArr[targetArr[i]] != targetArr[i]){
                        int temp = targetArr[i];
                        targetArr[i]=targetArr[temp];
                        targetArr[temp] =temp;
                        if(temp < i)
                            break;
                    }else {
                        System.out.println(targetArr[i]);
                        break;
                    }
                }else {
                    break;
                }

            }
        }

    }

    public static void main(String[] args) {
//        int num = 10;
//        for (int i = 0; i < num; i++) {
//
//            int[] arr = ArrayProducer.produce(num, 0, num - 1);
//            find(arr);
//
//        }

        int[] arr = {1, 2, 1};
        find(arr);


    }
}
